import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-20-有效的括号
 * @date 2025/6/4 11:41
 */
public class Solution20 {
    public boolean isValid(String s) {
        int n = s.length();
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                queue.push(0);
            } else if (s.charAt(i) == '{') {
                queue.push(1);
            } else if (s.charAt(i) == '[') {
                queue.push(2);
            } else {
                // 右括号，出栈
                int flag = -1;
                if (queue.isEmpty()) {
                    return false;
                }
                int left = queue.pop();
                if (s.charAt(i) == ')') {
                    flag = 0;
                } else if (s.charAt(i) == '}') {
                    flag = 1;
                } else {
                    flag = 2;
                }
                if (flag != left) return false;
            }
        }
        return queue.isEmpty();
    }
}
